package gold.digger;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC430 {
    public long startExecuteTime = System.currentTimeMillis();


    // Definition for a Node.
    public class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;

        public Node(int val) {
            this.val = val;
        }
    }

    class Solution {
        public Node flatten(Node head) {
            if (null == head) return null;
            return flattenRecur(head).getKey();
        }

        public Pair<Node, Node> flattenRecur(Node head) {
            if (null == head) return null;
            Node cur = head, prev = head;

            while (null != cur) {
                while (null != cur && null == cur.child) {
                    prev = cur;
                    cur = cur.next;
                }
                if (null == cur) return new Pair<>(head, prev);
                Pair<Node, Node> curChildSubList = flattenRecur(cur.child);
                cur.child = null;
                Node next = cur.next;
                cur.next = curChildSubList.getKey();
                curChildSubList.getKey().prev = cur;

                curChildSubList.getValue().next = next;
                if (null != next) next.prev = curChildSubList.getValue();
                prev = curChildSubList.getValue();
                cur = next;
            }

            return new Pair<>(head, prev);
        }
    }

    public void run() {
        Solution solution = new Solution();
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);

        n1.child = n2;
        n2.child = n3;


//        Node n1 = new Node(1);
//        Node n2 = new Node(2);
//        Node n3 = new Node(3);
//        Node n4 = new Node(4);
//        Node n5 = new Node(5);
//        Node n6 = new Node(6);
//        Node n7 = new Node(7);
//        Node n8 = new Node(8);
//        Node n9 = new Node(9);
//        Node n10 = new Node(10);
//        Node n11 = new Node(11);
//        Node n12 = new Node(12);
//
//        n1.next = n2;
//        n2.next = n3;
//        n3.next = n4;
//        n4.next = n5;
//        n5.next = n6;
//        n7.next = n8;
//        n8.next = n9;
//        n9.next = n10;
//        n11.next = n12;
//
//        n3.child = n7;
//        n8.child = n11;

        Node re = solution.flatten(n1);
        System.out.println(re);
    }

    public static void main(String[] args) throws Exception {
        LC430 an = new LC430();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
